Can Place Flowers

605. Can Place Flowers

題目敘述

題目要求我們判斷是否可以在一個花壇中種入指定數量的花，而不違反規則。具體規則是，花不能種在相鄰的位置。即種下去的花左右兩邊都必須要是空位。

你需要根據給定的花壇陣列flowerbed和需要額外種的花數量 n，判斷是否能夠在這個花壇裡種入 n 朵花。

解題思路

這題的關鍵在於如何判斷是否可以在當前的花壇中種下花，而不違反「相鄰位置不能種花」的規則。具體來說，我們要找到一個空位，並且這個空位的左右兩邊（如果存在）也必須是空的。

解題思路如下：

1. 如果 n 等於 0，則直接返回 True，因為不需要種任何花。
2. 我們遍歷整個花壇 flowerbed，檢查每一個位置：
   • 如果當前位置是空的（即 flowerbed[i] == 0），並且：
     • 它是花壇的第一個位置，或者它的左邊也是空的（i == 0 or flowerbed[i-1] == 0）。
     • 它是花壇的最後一個位置，或者它的右邊也是空的（i == len(flowerbed) - 1 or flowerbed[i+1] == 0）。
   • 那麼，我們可以在這個位置種下一朵花，並且將 n 減 1。
3. 如果在迴圈過程中，n 減到 0，則返回 True。
4. 如果遍歷完所有位置後，仍無法種滿 n 朵花，則返回 False。

通過這種方式，我們可以在遍歷一次花壇的時間內解決問題，時間複雜度是 O(n)。

程式碼

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:

        if n == 0:
            return True
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i+1] == 0):
                flowerbed[i] = 1
                n -= 1
                if n == 0:
                    return True
        return False

小結

在寫此題的時候讓我想到了男廁小便斗的問題。俗稱的男廁一三五法則:男生在上廁所的時候旁邊不能有人，所以要上第一、第三、第五間小便斗。這個概念跟此題要問的十分相似。